package pojo

import (
	"fmt"
	"strings"
)

type BinaryTree struct {
	Value int
	Left  *BinaryTree
	Right *BinaryTree
}

func NewBinaryTree(value int) *BinaryTree {
	return &BinaryTree{Value: value}
}

type MyType interface {
	int | *BinaryTree | string
}
type node1[T MyType] struct {
	Value T
	Next  *node1[T]
}

type Queue1[T MyType] struct {
	head *node1[T]
	tail *node1[T]
	Size int
}

func NewQueue1[T MyType]() *Queue1[T] {
	return &Queue1[T]{}
}

func (receiver *Queue1[T]) QueueSize() int {
	return receiver.Size
}

func (receiver *Queue1[T]) IsEmpty() bool {
	return receiver.Size == 0
}
func (receiver *Queue1[T]) Offer(v T) {
	var n = node1[T]{
		Value: v,
		Next:  nil,
	}
	if receiver.head == nil {
		receiver.head = &n
		receiver.tail = &n
	} else {
		receiver.tail.Next = &n
		receiver.tail = &n
	}

	receiver.Size++
}
func (receiver *Queue1[T]) Poll() T {
	var v T
	if receiver.Size == 0 {
		receiver.head, receiver.tail = nil, nil

	} else if receiver.Size == 1 {
		v = receiver.head.Value
		receiver.head = nil
		receiver.tail = nil
		receiver.Size--

	} else {
		v = receiver.head.Value
		receiver.head = receiver.head.Next
		receiver.Size--
	}
	return v

}
func (receiver Queue1[T]) Peek() T {
	var v T

	if receiver.head != nil {
		v = receiver.head.Value
	}

	return v
}
func CengJiBianLi(tree *BinaryTree) []int {
	if tree == nil {
		return nil
	}

	return f(tree)
}

func f(tree *BinaryTree) []int {
	arr := []int{}
	queue1 := NewQueue1[*BinaryTree]()

	queue1.Offer(tree)
	for !queue1.IsEmpty() {

		upNode := queue1.Poll()
		if upNode.Left != nil {
			queue1.Offer(upNode.Left)
		}
		if upNode.Right != nil {
			queue1.Offer(upNode.Right)
		}

		arr = append(arr, upNode.Value)

	}
	return arr
}

func PrintBinaryTree(node *BinaryTree) {

}

type Node struct {
	Val       int
	Childrens []Node
}

func NewNodeByInt(val int) *Node {
	return &Node{Val: val}
}

func NewNode(val int, childrens []Node) *Node {
	return &Node{Val: val, Childrens: childrens}
}

func PrintTree(root *BinaryTree) {
	if root == nil {
		return
	}
	// get the height of the tree
	height := getHeight(root)
	// get the width of the last level
	width := 1 << height
	// create a 2D slice to store the tree values
	matrix := make([][]string, height)
	for i := range matrix {
		matrix[i] = make([]string, width)
		for j := range matrix[i] {
			matrix[i][j] = " "
		}
	}
	// fill the matrix with the tree values using DFS
	fillMatrix(root, matrix, 0, 0, width-1)
	// print the matrix line by line
	for _, row := range matrix {
		fmt.Println(strings.Join(row, ""))
	}
}

// getHeight returns the height of the tree
func getHeight(root *BinaryTree) int {
	if root == nil {
		return 0
	}
	leftHeight := getHeight(root.Left)
	rightHeight := getHeight(root.Right)
	if leftHeight > rightHeight {
		return leftHeight + 1
	}
	return rightHeight + 1
}

// fillMatrix fills the matrix with the tree values using DFS
func fillMatrix(root *BinaryTree, matrix [][]string, level, left, right int) {
	if root == nil || level >= len(matrix) {
		return
	}
	mid := (left + right) / 2
	matrix[level][mid] = fmt.Sprint(root.Value)
	fillMatrix(root.Left, matrix, level+1, left, mid-1)
	fillMatrix(root.Right, matrix, level+1, mid+1, right)
}
